package everyday.nowcoder;
import java.util.*;
/**
 * @Author: wenjingyuan
 * @Date: 2022/10/27/22:44
 * @Description:NC41 最长无重复子数组（重点）
 * 思路：使用两个指针，一个i一个j，最开始的时候i和j指向第一个元素，然后i往后移，
 * 把扫描过的元素都放到map中，如果i扫描过的元素没有重复的就一直往后移，
 * 顺便记录一下最大值max，如果i扫描过的元素有重复的，就改变j的位置（将j的位置设置为重复元素的下标+1）。
 *
 * 需要注意的点
 * 更新 j 值的时候不是j++，而是将 j 放在map.get(arr[i]) + 1处，其中（map.get(arr[i])）指的是重复数字的下标
 * 每次都更新一下max，max(max, i - j + 1)
 */
public class NumNC41 {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
     if(arr.length==0){
         return 0;
     }
     HashMap<Integer,Integer> map=new HashMap<>();
     //最大的数字
     int max=1;
     int j=0;
     for (int i = 0; i <arr.length ; i++) {
         if(map.containsKey(arr[i])){
             //如果i下标的值重复了，则把起始位置j调整，调整为此时重复i的下一个索引
             j=Math.max(j,map.get(arr[i])+1);
            }
         //将i索引的值放进去，下标放进去是因为j需要下标
            map.put(arr[i],i);
         //最后选择哪个最大的下标，用之前的max和不重复的i-j+1得到个数，选择较大的值
            max=Math.max(max,i-j+1);
        }
        return max;
    }
}
